Kodumaro :: Brainfuck (parte 3) – Cabeçote e microprograma

Publicado em 14 de Dezembro, 2017
As sombras da programação.
Máquina de Turing

Agora falta criar a lógica de fato do interpretador, criando o cabeçote de leitura e o microprograma. O cabeçalho do arquivo parser.pl será:

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

Pois usaremos a fita e a memória, e precisaremos do predicado finally/2 do submódulo utils.pl.

O ponto de entrada será o predicado parse/1, que receberá o nome do arquivo da fita, criará a fita e executará os comandos do microprograma para os símbolos do alfabeto contidos na fita. Usaremos finally/2 porque, ao final, independente do que acontecer, a fita deverá ser fechada.

parse(Filename) :- create_tape(Filename, Tape),
                   finally(parse_tape(Tape),
                           close(Tape)).

Para exportar o predicado, alteramos o cabeçalho:

:- module(parser, [parse/1]).

Analizando a fita

Para analisar a fita, parse_tape/1 precisa ler a fita, executar a ação

e passar para a próxima ação:
parse_tape(Tape) :- read_tape(Tape, Statement),
                    perform(Tape, Statement),
                    parse_tape(Tape).

Mas antes disso, é preciso verificar se a fita já acabou! Se acabou, não há mais nada o que fazer, apenas encerrar:

parse_tape(Tape) :- end_of_tape(Tape), !.

Repare que preform/2 recebe a fita e a isntrução.

Manipulando a memória

As quatro primeiras instruções de Brainfuck (>, <, + e -) já estão prontas, foram implementadas no módulo de memória, é só repassar para os predicados corretos:

perform(_, >) :- !, next_slot(brainfuck).

perform(_, <) :- !, prev_slot(brainfuck).

perform(_, +) :- !, incr_slot(brainfuck).

perform(_, -) :- !, decr_slot(brainfuck).

Como não lida com a fita, nem precisamos nos preocupar com o primeiro parâmetro.

Entrada e saída (I/O)

As próximas duas instruções são as instruções de I/O. Para fazer a saída do valor da célula atual basta transformarmos o valor em um atom usando char_code/2 e realizarmos a saída usando write/1, porém, como a saída pode não apresentar mudança de linha, precisamos forçar o flush da saída com flush_output/0.

perform(_, .) :- !, get_slot(brainfuck, Value),
                 char_code(Show, Value),
                 write(Show),
                 flush_output.

E vois là! Já temos nossa saída.

Para a entrada de dados o processo também será tão simples quanto, lendo um atom de carácter da entrada padrão com get_char/1, convertendo para numérico também com char_code/2 e ajustando o slot da memória com set_lot/2.

No entanto há uma pegadinha! get_char/1 pode retornar end_of_file, e precisamos tratar isso. Apesar de o código ASCII mais coerente com end_of_file ser eot, ele não apresenta o comportamento desejado de encerramento de loops como costuma ser usado, então, em seu lugar, usaremos null.

Então o predicado principal chamará get_char/1 e repassará a responsabilidade para process_read/1:

perform(_, ',') :- !, get_char(Value),
                   process_read(Value).

Agora process_read/1 receberá um atom, que pode ser end_of_file ou a representação de um carácter. Tratando o primeiro caso:

process_read(end_of_file) :- !, set_slot(brainfuck, 0). % use NULL as EOF

No segundo caso precisamos converter o atom para código ASCII antes de chamar set_slot/2:

process_read(Value) :- char_code(Value, Num),
                       set_slot(brainfuck, Num).

Loops e condicionais

Agora vem a parte mais complicado. Ao abrir um bloco condicional, é preciso verificar se a célula (slot) atual é zero. Se for, o bloco será ignorado e é preciso procurar o fechamento deste bloco. Para tanto, usaremos um contador de blocos abertos:

perform(Tape, '[') :- get_slot(brainfuck, 0), !,
                      goto_close(Tape, 1).

Se não for zero – ou seja, esta verdade falhou – continua normalmente:

perform(_, '[') :- !.

Quanto ao fechamento de bloco condicional, como ele se comporta como um while, se a célula atual for zero, passa normalmente:

perform(_, ']') :- get_slot(brainfuck, 0), !.

Se não for, volta a fita até encontrar a abertura deste bloco, usando também um contador de blocos:

perform(Tape, ']') :- !, goto_open(Tape, 1).

Procurando o fechamento

O predicado goto_close/2 tem como efeito colateral correr pra frente a fita até o fechamento do bloco, o que ocorre quando o contador zera ou quando chega ao fim da fita:

goto_close(_, 0) :- !.

goto_close(Tape, _) :- end_of_tape(Tape), !.

Caso isso não ocorra, ele precisa ler a posição atual da fita e verificar se isso indica uma abertura ou fechamento de bloco:

goto_close(Tape, N) :- read_tape(Tape, Value),
                       check_close(Tape, N, Value).

Se for uma nova abertura de bloco, é preciso incrementar o contador e continuar da próxima posição da fita:

check_close(Tape, N, '[') :- !, succ(N, N1),
                             goto_close(Tape, N1).

Se for um fechamento de bloco, é preciso decrementar o contador e continuar:

check_close(Tape, N, ']') :- !, succ(N1, N),
                             goto_close(Tape, N1).

Se for qualquer outro carácter, continua como o mesmo contador:

check_close(Tape, N, _) :- goto_close(Tape, N).

Procurando a abertura

O predicado goto_open/2 tem como efeito colateral rebobinar a fita até a abertura do bloco, o que ocorre quando o contador zera ou quando chega ao início da fita:

goto_open(_, 0) :- !.

goto_open(Tape, _) :- start_of_tape(Tape), !.

Caso contrário, precisa rebobinar a fita e ler a posição atual, verificando abertura ou fechamento de bloco:

goto_open(Tape, N) :- tape_backward(Tape),
                      read_tape(Tape, Value),
                      check_open(Tape, N, Value).

A verificação de bloco ocorre quase da mesma forma que a anterior, apenas incrementando o contador quando encontra novo fechamento e decremento nas aberturas:

check_open(Tape, N, '[') :- !, succ(N1, N),
                            goto_open(Tape, N1).

check_open(Tape, N, ']') :- !, succ(N, N1),
                            goto_open(Tape, N1).

check_open(Tape, N, _) :- goto_open(Tape, N).

Comentários

Para Brainfuck, todo carácter desconhecido é um comentário, sendo ignorado:

perform(_, _). % ignore unknown characters

Arquivos

Conceitual | Lógica