read ::

Ouvi dizer que havia dificuldades em perceber como se definem instâncias da classe Read em Haskell, apesar das explicações dos professores. Esta é a minha tentativa de iluminar algumas mentes sobre isso.

Parece que há um trabalho sobre uma linguagem de programação estranha, mas que acho muito interessante chamada brainfuck. Não vi o enunciado, mas ao que parece é necessário fazer pelo menos uma instância de Show e de Read para os tipos que representam programas em brainfuck.

---

Introdução

Brainfuck foi criada para ser uma linguagem Turing-completa com o compilador mais pequeno possível. Uma linguagem para ser Turing-completa tem de permitir fazer tudo o que se pode fazer numa máquina de Turing. Uma máquina de Turing é, dito de uma forma simples, uma máquina teórica que manipula dados numa fita de comprimento infinito. A fita é composta por um número infinito de células de memória ao lado umas das outras. Podem pensar nisto como um array com tamanho infinito. A máquina de Turing tem uma cabeça que percorre a fita para trás e para a frente e altera as células de memória conforme o programa que está a correr dita.

O modelo de memória em brainfuck é exactamente este (embora esteja limitado fisicamente pela memória disponível na máquina): a memória é acedida desta forma, com uma única cabeça que se movimenta pela “fita” fora conforme os comandos dados no programa.

Os comandos em brainfuck são sete, representados pelos símbolos <>+–.,[]

• < e > são as operações de mover a cabeça uma célula para a esquerda e para a direita respectivamente.
• + e – são as operações de incrementar ou decrementar em uma unidade a célula onde está a cabeça
• . e , são respectivamente, o output da célula actual, e o input para a célula actual
• [ e ] servem para criar ciclos. Os comandos que estiverem entre estes caracteres são executados repetidamente até que, ao chegar ao fim de uma dessas execuções, i.e. ao chegar novamente ao ], o valor da célula actual seja zero.

Tipos de dados

Bem, não sei se isto era dado no enunciado ou não, mas estes são os tipos que vou usar para representar os programas:

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

BF representa um programa, i.e., uma lista de comandos. BFCommand representa um comando:

• IncPtr e DecPtr são “>” e “<”;
• IncVal e DecVal são “+” e “-”;
• Read e Print são “.” e “,”;
• While representa os comands entre “[” e “]”, e por isso tem como argumento essa lista de comandos.

Isto é fácil, faz mas é o que interessa!

Vou começar por definir instâncias de Show.

Show é uma classe em Haskell que é usada quando é necessária a representação textual de um valor.

Ao definir um tipo como instância desta classe podemos converter os seus valores em texto. Por exemplo, depois de instânciar Show para os dois tipos acima, vamos poder fazer isto no interpretador:

> BF [While (BF [DecVal, IncPtr, IncVal, DecPtr])]
[->+<]

Introduzindo a representação de um programa com os nossos tipos, o interpretador dá-nos a sua representação em texto, em brainfuck.

Como é que instanciamos classes em Haskell? Bem, cada classe requer que definamos um mínimo de funções para estar completa (em inglês isto chama-se “minimal complete definition”). A classe Show pode ser completamente definida apenas com uma função, chamada show. Quem sabe Java pode pensar nisto como definir o método toString numa classe.

class Show a where
    showsPrec :: Int -> a -> ShowS
    show :: a -> String
    showList :: [a] -> ShowS

As outras duas funções são definidas automaticamente se definirmos show. Como podemos ver, show recebe o tipo para o qual vamos instanciar a classe e produz uma string.

Definir show :: BF –> String e instanciar assim Show BF, vamos fazer pattern matching sobre a lista que serve de argumento em BF:

instance Show BF where
    show (BF []) = ""
    show (BF (h:t)) = -- ?

Se o programa não tiver instruções, a sua representação é uma string vazia. E se o programa tiver instruções?

Nesse caso a sua representação é a sequência das representações textuais das suas instruções. Ou seja, para o corpo do ciclo no programa acima, BF [DecVal, IncPtr, IncVal, DecPtr], vamos buscar as representações de cada uma das instruções (do tipo BFCommand) e juntámo-las numa string.

Mas como é que obtemos as representações textuais das instruções?

(continua…)