Vamos começar a construção de nosso interpretador Brainfuck pela fita.

A máquina de Turing é um conceito matemático teórico criado por Alan Turing que consiste em um modelo abstrato de uma máquina de estado capaz de executar tarefas genéricas.

A máquina de Turing é formada por quatro partes:

1. Uma fita dividida em células, cada uma representando uma instrução a ser executada. O tamanho da fita é o suficiente para representar a tarefa pretendida.
2. Um registro de estados de tamanho suficiente para executar a tarefa pretendida.
3. Um cabeçote que lê as instruções da fita e as executa de acordo com um alfabeto conhecido.
4. Um alfabeto conhecido com instruções que define ações como mover a fita ou alterar estados do registro.

Podemos traçar um paralelo com o computador moderno: a fita são as instruções dadas ao processador, o registro de estados é a memória, o cabeçote é o processador e o alfabeto é o microprograma do processador.

Brainfuck é uma linguagem de programação esotérica que implementa a máquina de Turing de forma extrema.

Recomendo o artigo na Wikipédia, que explica muito bem.

Vamos usar Prolog pra implementar o interpretador.

Criando a fita

Criaremos um arquivo chamado tape.pl para construir nossa fita. O cabeçalho de nosso arquivo será:

% -*- Prolog -*-
:- module(tape, []).

Por enquanto nada é exportado. Nosso primeiro predicado criará a fita a partir de um arquivo texto e terá a assinatura create_tape(+Filename, -Tape), sendo o primeiro objeto o nome do arquivo e o segundo o stream para sua leitura – a fita.

Para tanto vamos usar o predicado open/4, que abre um arquivo para streaming. Assim poderemos usar predicados padrão da linguagem para lidar com a fita, como close/1, get_char/2 e seek/4.

Vamos também criar um predicado start_of_tape/1 que verifica se a fita está no começo para podermos testar nossa fita.

Podemos escrever o teste no final do arquivo:

:- begin_tests(tape).

test(create_tape, [setup(create_tape('test.tape', Tape)),
                   cleanup(close(Tape)) ]) :-
  start_of_tape(Tape).

:- end_tests(tape).

Precisamos também de uma fita teste. No terminal execute:

sh> echo 12345 > test.tape

Então create_tape/2 terá a seguinte definição (coloque antes dos testes):

create_tape(Filename, Tape) :-
    open(Filename, read, Tape,
         [buffer(false), lock(read), wait(false)]).

Estamos abrindo o arquivo Filename sem buffering (buffer(false)), travado para leitura (lock(read), não queremos modificar a fita) e retornando um erro caso o arquivo não exista (wait(false)).

E start_of_tape/1 será:

start_of_tape(Tape) :- seek(Tape, 0, current, 0).

Essa foi uma trapaça: usamos seed/4 para mover o ponteiro para mesma posição em que ele já se encontrava e verificamos se a posição é zero.

Agora já podemos testar. No terminal rode:

sh> swipl -q -t run_tests. tape.pl
.

Sucesso! Agora é possível exportar o predicato. Vamos mudar a declaração do módulo para:

:- module(tape, [create_tape/1]).

Lendo a fita

Para ler a fita vamos usar get_char/2, e vamos criar um predicato end_of_tape/1 para testar se a fita chegou ao fim.

Como a fita é um stream, podemos usar at_end_of_stream/1 para tanto:

end_of_tape(Tape) :- at_end_of_stream(Tape).

Na seção de testes (entre begin_tests/1 e end_tests/1) vamos escrever o teste para ver se read_tape/2 se comporta de acordo:

test(read_tape, [setup(create_tape('test.tape', Tape)),
                 cleanup(close(Tape)) ]) :-
    start_of_tape(Tape),
    forall(
        member(X, [49, 50, 51, 52, 53, 10]),
        (
            read_tape(Tape, R),
            char_code(R, X)
        )
    ),
    end_of_tape(Tape).

Para cada elemento da fita test.tape, convertemos de atom para carácter (portanto tem de ser um atom) e verificamos se bate com o esperado.

Antes da leitura fazemos a verificação se está no começo da fita, ao final verificamos se chegou ao final.

Agora vamos à definição de read_tape/2.

Sua assinatura é read_tape(+Tape, -Statement), e podemos defini-lo como:

read_tape(Tape, Statement) :- get_char(Tape, Statement).

Voltemos ao teste:

sh> swipl -q -t run_tests. tape.pl
..

Sétimo andar e tudo bem até aqui…

Expondo o novo predicado:

:- module(tape, [create_tape/1, read_tape/1]).

Recuando a fita

Ao ler a fita, ela já anda para a próxima célula, mas precisamos poder recuar a fita.

Para tanto vamos criar o predicado tape_backward/2. Para facilitar os testes, podemos criar também um predicado tape_foward/2.

Na seção de testes, podemos escrever nosso novo teste:

test(tape_backward, [setup(create_tape('test.tape', Tape)),
                     cleanup(close(Tape))]) :-
    start_of_tape(Tape),
    tape_forward(Tape, 3),
    tape_backward(Tape, 1),
    read_tape(Tape, '3').

Assim avançamos três células a partir do começo e recuamos uma, precisa retornar o atom '3'.

Podemos começar com nosso predicado auxiliar:

tape_forward(Tape, Steps) :- seek(Tape, Steps, current, _).

Usamos seek/4 para avançar a fita Steps passos a partir da posição atual (current).

O predicado principal pode tirar proveito desse:

tape_backward(Tape, Steps) :- BackwardSteps is -1 * Steps,
                              tape_forward(Tape, BackwardSteps).

Simplesmente recuar é avançar passos negativos! Os testes agora:

sh> swipl -q -t run_tests. tape.pl
...

O uso mais frequente de de tape_backward/2 será com dois passos para trás, então podemos criar um predicado facilitador:

tape_backward(Tape) :- tape_backward(Tape, 2).

Finalizando

Vamos precisar também exportar os predicador start_of_tape/1 e end_of_tape/1, serão úteis. Assim o cabeçalho de nosso módulo termina assim:

% -*- Prolog -*-
:- module(tape, [create_tape/2, read_tape/2, tape_backward/1, end_of_tape/1,
          start_of_tape/1]).

Download do arquivo:

No próximo artigo vamos ver o registro de estados.