read :: Read a => String –> a

(continuando…)

readsPrec usando readsPrec usando readsPrec

Bem, tal como fizemos com o Show, vamos começar por Read BFCommand, fazer tudo menos o While, fazer o Read BF à custa do Read BFCommand, e depois acabar a parte do While no Read BFCommand à custa do Read BF. Espero que isto não vos dê a volta a cabeça…

A função read consome o texto todo e devolve um valor. A função readsPrec no entanto, só consome um pouco de cada vez. Por isso, a função readsPrec :: Int –> ReadS BFCommand vai (exceptuando o caso do While) consumir apenas um caractere do texto e produzir imediatamente uma lista com um par (representação do caractere consumido, resto do texto):

instance Read BFCommand where
    readsPrec _ ('>':s) = [(IncPtr, s)]
    readsPrec _ ('<':s) = [(DecPtr, s)]
    readsPrec _ ('+':s) = [(IncVal, s)]
    readsPrec _ ('-':s) = [(DecVal, s)]
    readsPrec _ (',':s) = [(Read, s)]
    readsPrec _ ('.':s) = [(Print, s)]
    readsPrec _ s = [] -- o While já custa mais

Reparem que estamos a ignorar o nível de prioridade, porque em brainfuck isso não faz diferença.

Com isto já podemos experimentar ler BFCommands:

> (read "-")::BFCommand
DecVal
> (read "+")::BFCommand
IncVal
> (read "[-]")::BFCommand
*** Exception: Prelude.read: no parse

Para testar o read comentei a instância de Show e adicionei deriving Show aos tipos BF e BFCommand. Assim podemos ver a representação em Haskell (p.e. DecVal e IncVal) em vez de vermos exactamente o texto original (- e +).

Reparem ainda que para o caso do While obtemos “no parse”. Isto é porque devolvemos uma lista vazia para esse caso.

Devem ter reparado que tornei explícito o tipo ao invocar read no interpretador. Isto é porque o interpretador não adivinha que queremos ler um BFCommand. Poderiamos querer ler um BF, por exemplo.

Passando então ao Read BF…

Como já tinhamos visto, vamos ter de recorrer ao readsPrec para BFCommand. Como esta função devolve uma lista vamos fazer pattern matching:

    readsPrec p s = case readsPrec p s of
                        [] -> -- ?
                        xs -> -- ?

O que devolvemos quando não temos comandos? Um programa vazio: BF []. Mas não esquecer que readsPrec devolve a tal lista de pares (resultado, resto do texto):

    readsPrec p s = case readsPrec p s of
                        [] -> [(BF [], s)]
                        xs -> -- ?

E quando temos pelo menos um comando? Neste caso xs é uma lista de pares (BFCommand, String). Temos de entrar recursivamente no texto que sobra, e ir juntando comandos ao resultado.

Usando listas por compreensão, e pattern matching, podemos construir o resultado que queremos. Em primeiro lugar temos de fazer pattern matching com xs para extrair as partes do par que está em xs. Depois de termos o comando de xs e o resto do texto, chamamos readsPrec recursivamente no texto que sobra, para ler o resto dos comandos. Assim ficamos com uma lista [(BF, String)].

De cada um destes pares queremos as listas de comandos que constituem o BF, e queremos o texto que falta. Para isso vamos usar pattern matching novamente.

Até aqui temos isto:

                        xs -> [(..., ...) | -- Queremos pares como resultado
                                  (c, t) <- xs, -- Pattern matching em xs
                                  (BF cs, u) <- readsPrec p t] -- Ler o resto do texto e fazer pattern matching

Agora falta-nos descobrir como construir os pares do resultado:

• têm de ser do tipo (BF, String);
• o texto que sobra é u, porque t já foi processado na chamada recursiva;
• o resultado é um programa com o primeiro comando lido (c) e com os que foram lidos na chamada recursiva (cs).

Fica então assim:

instance Read BF where
    readsPrec p s = case readsPrec p s of
                        [] -> [(BF [], s)]
                        xs -> [(BF (c:cs), u) |
                                   (c, t) <- xs,
                                   (BF cs, u) <- readsPrec p t]

Agora podemos experimentar tudo menos Whiles:

> (read "-+")::BF
BF [DecVal,IncVal]
> (read "->+<")::BF
BF [DecVal,IncPtr,IncVal,DecPtr]

Então vamos aos Whiles. Vamos usar a mesma estratégia: listas por compreensão e pattern matching. Mas também vamos usar uma função chamada lex.

> :i lex
lex :: ReadS String

Esta função é aquilo que em processamento de linguagens se chama um analisador léxico (lexer em inglês). Esta função lê um lexema da linguagem Haskell de cada vez. O que isto quer dizer é que serve para partir código Haskell nas suas partes constituintes. Talvez um exemplo ajude a perceber:

> lex "[10,20,30]"
[("[","10,20,30]")]
> lex "10,20,30]"
[("10",",20,30]")]
> lex ",20,30]"
[(",","20,30]")]
> lex "20,30]"
[("20",",30]")]
> lex ",30]"
[(",","30]")]
> lex "30]"
[("30","]")]
> lex "]"
[("]","")]

Aqui começamos com uma lista e gradualmente vamos retirando partes: primeiro o parentesis recto de abertura, depois o número 10, depois a vírgula, depois o número 20, mais outra vírgula, o número 30, e por fim o parentesis de fecho.

Com esta função podemos ler os parentesis rectos e ficar com o resto para ser lido recursivamente. Vai ser algo semelhante a isto:

    readsPrec p s = [(...,...) | -- Queremos pares
                        ("[",t) <- lex s, -- Ler o [
                        (bf,u) <- readsPrec p t, -- Ler recursivamente um BF
                        ("]",v) <- lex u] -- Ler o ]

Reparem que o texto que sobra vai sendo passado de umas funções para as outras, primeiro para lex, depois readsPrec e finalmente lex novamente para ler o último “]”.

Agora só falta construir os pares que queremos.

• têm de ter o tipo (BFCommand, String) porque estamos a ler BFCommands;
• o texto que sobra é o que ficou no fim: v;
• o comando é um While que corre os comandos que foram lidos em bf;

Ficamos então com:

    readsPrec p s = [(While bf, v) |
                        ("[",t) <- lex s,
                        (bf,u) <- readsPrec p t,
                        ("]",v) <- lex u]

(fim?)