run :: BF -> IO ()

(continuando…)

A representação da máquina que usamos até aqui (um par com o índice onde está a cabeça, e a lista com as células) não é muito eficiente, porque é necessário percorrer a lista recursivamente para ler ou alterar o valor da célula actual.

Existe uma outra forma de representar a máquina que é muito mais eficiente. Basicamente, consiste em usar duas listas: uma para as células à esquerda da cabeça e outra para as células à direita. Sempre que avançamos com a cabeça para a direita (incrementar), passamos a célula actual para a lista da esquerda. Sempre que avançamos para a esquerda, a célula actual passa para a lista da direita.

O truque para implementar isto de forma simples consiste em manter a lista da esquerda pela ordem inversa, i.e., a cabeça representa a primeira célula à esquerda, e não a última.

Desta forma, todas as operações são feitas sempre nas cabeças das listas, o que, para além de ser simples de implementar, é bastante eficiente.

Para implementar o interpretador desta forma basta fazer estas alterações:

type Memoria = ([Int], [Int])

emptyMem :: Memoria
emptyMem = ([0,0..],[0,0..])

incPtr :: Memoria -> Memoria
incPtr (l,rh:rt) = (rh:l,rt)

decPtr :: Memoria -> Memoria
decPtr (lh:lt,r) = (lt,lh:r)

incVal :: Memoria -> Memoria
incVal (l,h:r) = (l,h+1:r)

decVal :: Memoria -> Memoria
decVal (l,h:r) = (l,h-1:r)

writeVal :: Int -> Memoria -> Memoria
writeVal x (l,_:r) = (l,x:r)

readVal :: Memoria -> Int
readVal (_,h:_) = h

Aqui assumi que a célula actual é a que está na cabeça da direita. Para ser a da esquerda, bastava ter isso em atenção nas funções que manipulam a célula actual e não o apontador. Também era possível manter a célula actual fora de ambas as listas, mas isso tornaria as coisas ligeiramente mais difíceis.

Estas versões das funções são muito mais simples, mas o princípio de funcionamento é um pouco mais complicado. Reparem ainda que desta forma a fita pode ser infinita em ambos os sentidos.

(nota: os mais avançados poderão reconhecer as duas listas como duas stacks. Basicamente, avançar para a direita é fazer pop da stack da direita e push desse elemento na esquerda. Avançar para a esquerda é o contrário.)