Kodumaro :: Brainfuck (parte 2) – A memória

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

O próximo elemento do interpretador Brainfuck será a memória.

O módulo memory.pl comerçará com o seguinte cabeçalho:

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

Vamos precisar de um módulo auxiliar com alguns metapredicados úteis. Aqui utilizaremos optional/1, que valida um outro predicado, resolvendo positivamente mesmo que o predicado parâmetro falhe.

Ele possui outro predicado útil, finally/2, que usaremos mais para frente.

Para que nossa memória possa armazenar estados, precisaremos de dois predicados dinâmicos para armezanar as células de estado (slots) e a posição da memória.

Declaramos esses predicados no cabeçalho da seguinte forma:

:- dynamic slot/3, pos/2.

Usando a sintaxe de tipos de must_be/2, cada estado terá o formato slot(name:atom, position:integer, value:integer), onde name é o nome da memória, position a posição da memória e value o valor armazenado. Respeitando os tipos, os três parâmetros são arbitrários. Cada marcador de posição terá o formato pos(name:atom, position:integer), onde name é o nome da memória e position a posição atual.

Auxiliares para lidar com a posição da memória

Como precisamos de um valor padrão quando a posição não estiver definida, vamos criar dois predicados auxiliares get_pos/2 e set_pos/2.

O primeiro predicado precisa validar o valor do predicado dinâmico, se não resolver, resolve o valor para zero:

get_pos(Name, Pos) :- pos(Name, Pos), !.
get_pos(_, 0).

O segundo predicado precisa retrair a verdade atual do predicado e criar uma nova verdade. Para que a retração não falhe, usaremos optional/1:

set_pos(Name, Pos) :- optional(retract(pos(Name, _))),
                      assertz(pos(Name, Pos)).

Pegando o valor do slot de memória

O predicado que valida o valor em memória deve considerar a célula atual, cuja posição é definida por get_pos/2. Portanto get_slot/2 deve consultar a posição atual e repassar a responsabilidade para get_slot/2 usando tail-call optimisation:

get_slot(Name, Value) :- get_pos(Name, Pos),
                         get_slot(Name, Pos, Value).

Ao contrário do artigo anterior, não vou comentar os testes, mas você pode vê-los no código fonte.

A primeira verdade de nosso perdicado é quando coincide com alguma verdade do predicado dinâmico:

get_slot(Name, Pos, Value) :- slot(Name, Pos, Value), !.

A segunda verdade é que o valor é zero se não existir uma verdade que coincida com o nome e a posição no predicado dinâmico:

get_slot(Name, Pos, 0)     :- \+ slot(Name, Pos, _).

O metapredicado \+/1 verifica se o predicado parâmetro falha.

Agora precisamos de um predicado para mudar o valor da célula atual. Será regulado pelo mesmo princípio do getter:

set_slot(Name, Value) :- get_pos(Name, Pos),
                         set_slot(Name, Pos, Value).

Enquanto set_slot/3 se comportará de modo parecido a set_pos/2, retraindo a verdade atual e criando a nova:

set_slot(Name, Pos, Value) :- optional(retract(slot(Name, Pos, _))),
                              assertz(slot(Name, Pos, Value)).

Agora vamos exportar nossos predicados alterando o cabeçalho:

:- module(memory, [get_slot/2, set_slot/2]).

Incremento e decremento

As operações mais comuns de mudança de valor de célula são incremento e decremento. Podemos implementá-las usando os predicados que já temos:

incr_slot(Name) :- get_slot(Name, Value),
                   succ(Value, NewValue),
                   set_slot(Name, NewValue).

decr_slot(Name) :- get_slot(Name, Value),
                   succ(NewValue, Value),
                   set_slot(Name, NewValue).

O predicado succ/2 calcula o valor sucessor ou antecessor de valores naturais. Usando notação λ, sucessor e antecessor são definidos como:

SUCC := λx.sx
PRED := λ(sx).x

Fazendo a equivalência em Prolog:

succ(X, S(X)).

Exportando agora:

:- module(memory, [get_slot/2, set_slot/2, incr_slot/1, decr_slot/1]).

Mudando de célula

As operações para mudança de célula são mover para a próxima ou para a anterior, e são muito parecidas com incremento e decremento, a diferença é que, em vez do valor da célula, quem é incrementada ou decrementada é a posição:

next_slot(Name) :- get_pos(Name, Pos),
                   succ(Pos, NewPos),
                   set_pos(Name, NewPos).

prev_slot(Name) :- get_pos(Name, Pos),
                   succ(NewPos, Pos),
                   set_pos(Name, NewPos).

Ao exportarmos, teremos terminado nossa memória:

:- module(memory, [get_slot/2, set_slot/2, incr_slot/1, decr_slot/1
                   next_slot/1, prev_slot/1]).

Arquivos

Conceitual | Lógica