run ::

Na sequência da série de posts sobre a escrita de instâncias de Show e de Read em Haskell, este post trata da implementação de um interpretador de brainfuck.

Este interpretador terá de efectuar tanto input como output, e por isso deverá usar o tipo de dados paramétrico IO. Este tipo de dados costuma causar confusão nos aprendizes de Haskell por várias razões, algumas das quais são:

• input e output não encaixa muito bem com o paradigma funcional;
• é costume usar-se uma notação especial para trabalhar com dados deste tipo (a notação do);
• não existe uma função :: IO a –> a, por isso quando se usa IO uma vez, este “fica para sempre”;
• IO é um mónade, e muita gente tem pesadelos com isso.

Pessoalmente, este tema (I/O em Haskell) fica junto com recursividade, mónades e apontadores: temas muito mais simples do que se pintam. Vamos ver se consigo demonstrar esta simplicidade neste post.

Representações

Mais uma vez, vou começar pelos tipos de dados. Para representar programas, vou reutilizar os tipos utilizados anteriormente:

data BF = BF [BFCommand]
data BFCommand = IncPtr | DecPtr | IncVal | DecVal | Read | Print | While BF

Mas não nos basta representar os programas. Temos de representar também a máquina de Turing onde os programas serão executados. A máquina consiste basicamente numa série de células de memória e uma cabeça que as manipula. Uma forma simples de representar esta máquina poderia ser esta:

type Memoria = (Int, [Int])

Neste par, o primeiro elemento é o índice da célula onde a cabeça se encontra e o segundo elemento é a fita de memória. Agora podemos escrever umas funçõezitas para efectuar as operações básicas do nosso interpretador.

Onde está a dificuldade?

Uma dificuldade que encontro com frequência quando tento explicar isto é quando as pessoas não conseguem separar o input e o output das operações puramente funcionais. Por exemplo, imaginem que para este interpretador decidiam escrever as seguintes funções:

runIncPtr :: Memoria -> IO Memoria
runDecPtr :: Memoria -> IO Memoria
runIncVal :: Memoria -> IO Memoria
runDecVal :: Memoria -> IO Memoria
runRead :: Memoria -> IO Memoria
runPrint :: Memoria -> IO Memoria
runWhile :: BF -> Memoria -> IO Memoria

De todas estas, apenas as últimas três necessitam de ser escritas com IO pelo meio (While pode ter Reads e Prints no seu bloco), porque as quatro primeiras não fazem input nem output nenhum. Podiam ser simplesmente:

incPtr :: Memoria –> Memoria
decPtr :: Memoria -> Memoria
incVal :: Memoria –> Memoria
decVal :: Memoria -> Memoria

Cada um destas recebe o estado actual da máquina e produz um estado novo alterado de acordo com o funcionamento do comando BF.

Agora digam-me: por mais complicado que seja IO, onde está a dificuldade em escrever estas quatro funções? Nenhuma delas tem IO!

E reparem nisto: Read lê um número do teclado e escreve-o na célula actual; Print lê o valor da célula actual e escreve-o no ecrã. Em cada uma destas operações existem duas partes distintas: uma de manipulação da memória e uma de input/output. Se separarmos estas duas partes, tornamos mais simples a escrita de cada uma delas (embora aqui nenhuma das partes seja particularmente complicada :P)

writeVal :: Int -> Memoria -> Memoria
readVal :: Memoria -> Int
inVal :: IO Int
outVal :: Int -> IO ()

runRead :: Memoria -> IO Memoria
runRead m = do x <- inVal
               return (writeVal x m)

runPrint :: Memoria -> IO Memoria
runPrint m = do outVal (readVal m)
                return m

Reparem como as funções runRead e runPrint são simples. E escrever as outras quatro também é fácil, porque cada uma faz uma coisinha pequena.

As simples primeiro

As duas funções de manipulação da cabeça são muito simples: basta incrementar ou decrementar o primeiro elemento do par.

incPtr :: Memoria -> Memoria -- i.e. (Int, [Int]) -> (Int, [Int])
incPtr (p,m) = (p+1,m)

decPtr :: Memoria -> Memoria -- i.e. (Int, [Int]) -> (Int, [Int])
decPtr (p,m) = (p-1,m)

As de manipulação da célula actual já se tornam um pouco mais complexas (mas não muito): é necessário obter o valor da célula na posição da cabeça, e criar uma lista nova com essa célula alterada. Pela natureza das listas, isto implica percorrer a lista recursivamente até encontrar a célula desejada.

incVal :: Memoria -> Memoria
incVal (p,l) = (p,incVal' p l)
               where incVal' 0 (h:t) = h+1:t
                     incVal' i (h:t) = h:incVal' (i-1) t

decVal :: Memoria -> Memoria
decVal (p,l) = (p,decVal' p l)
               where decVal' 0 (h:t) = h-1:t
                     decVal' i (h:t) = h:decVal' (i-1) t

Basicamente cada uma das funções auxiliares percorre a lista recursivamente diminuindo o indice até chegar a zero. Quando o índice é zero, basta alterar o elemento que está na cabeça.

As duas que não usam IO que faltam, readVal e writeVal, também são semelhantes:

writeVal :: Int -> MemoriaA -> MemoriaA
writeVal n (x,l) = (x,writeVal' x l)
                   where writeVal' 0 (_:t) = n:t
                         writeVal' i (h:t) = h:writeVal' (i-1) t

readVal :: MemoriaA -> Int
readVal (x,l) = readVal' x l
                where readVal' 0 (h:_) = h
                      readVal' i (_:t) = readVal' (i-1) t

E finalmente: IO

Falta-nos agora as funções que usam IO. Como isolamos bem as coisas basta-nos escrever as funções inVal e outVal para termos runRead e runPrint a funcionar.

Antes de mais, vou falar rapidamente da notação do e do seu uso com IO. A notação do é uma comodidade que serve para escrevermos código com mónades (como é o caso de IO) de uma forma fácil de compreender e de escrever. No caso de IO, quando usamos a notação do o que acontece é que as linhas que escrevemos são “executadas” em sequência.

Existem algumas regras simples para seguir: todas as linhas tem de ser do tipo IO a, embora o a possa ser diferente para cada linha; e sempre que for necessário obter o a de um IO a, usamos:

  do ...
     x <- valueOfTypeIO
     ...

Aqui x vai servir para nos referirmos ao valor que está no valueOfTypeIO. Por exemplo, para ler uma linha de texto do teclado, usamos a função getLine :: IO String. Esta função lê uma linha e produz essa linha como uma string, mas num IO. Como essa linha vem num IO é necessário usar a notação com <- para podermos usar essa string em mais cálculos.

Mas porque é que getLine não é simplesmente do tipo :: String? Bem, isto é porque em Haskell, as funções não podem devolver valores diferentes sempre que são invocadas com os mesmos argumentos. Como getLine tem de poder produzir valores diferentes de cada vez (para podermos ler mais que uma linha!) não pode ser do tipo String. Tem de ser do tipo IO String, que para já podem tratar como um tipo mágico que permite fazer este tipo de “batota”. O preço a pagar é que agora, todas as funções que usem estas funções, não vão produzir sempre o mesmo resultado, e por isso têm de ter também IO no tipo de retorno. Quando (se) aprenderem mónades IO vai deixar de ser algo completamente mágico para passar a ser um mónade mágico. Bem, não é grande melhoria, mas é o que se arranja.

Bem, podemos então escrever inVal de uma forma simples, porque precisamos apenas de ler uma linha e convertê-la de String para Int. Já conhecem uma função que faz isto: read :: String –> Int, que existe porque Int é uma instância da classe Read:

> :i Int
data Int = ... cenas ...
... várias instâncias ...
instance Read Int
... várias instâncias ...

Podemos então escrever:

inVal :: IO Int
inVal = do l <- getLine
           read l -- Aqui não é necessário explicitar o tipo porque
                  -- o interpretador consegue inferir a partir do tipo
                  -- da função

Mas… estamos a violar a regra de que todas as instruções têm de ser do tipo IO a porque neste caso read l é do tipo Int. Precisamos de uma função Int –> IO Int. Ou a –> IO a. Essa função existe e chama-se return.

Ficamos então com:

inVal :: IO Int
inVal = do l <- getLine
           return (read l)

Agora, para escrever outVal temos de mostrar o argumento no ecrã. Reparem que o tipo da função é Int –> IO (), porque esta recebe um Int e faz I/O, mas não produz nenhum resultado. Para isto existe uma função que serve para mostrar no ecrã valores de tipos com instâncias de Show definidas (que é o caso para Int):

outVal :: Int -> IO ()
outVal x = print x

Agora tanto runRead como runPrint já funcionam.

(continua…)