15 de agosto de 2012

Programação funcional pura e útil

Acho que todos os programadores acostumados com o modelo imperativo ficam espantados em imaginar quão maluco é o modelo funcional puro. Afinal, como podemos fazer qualquer coisa útil sem gerar efeitos colaterais? Sem imprimir no console? Sem abrir uma tela? Sem gerar logs? Sem alterar variáveis? OMG.

Este também foi um espanto meu ao conhecer Haskell e por uma feliz insistência descobri que o problema está na cabeça do programador e não no modelo funcional puro.

Diferenças

Viver muito tempo no contexto das linguagens imperativas acabou modelando minha forma de pensar em uma maneira sequêncial. Eu sempre precisei dizer como fazer cada passo da computação, quais estados manter, quais variáveis alterar, quando retornar um valor, etc.

Enquanto que no mundo funcional puro, fui obrigado a pensar em uma maneira de transformação de dados. Ao invés de pensar em como fazer cada etapa, preciso pensar como transformar um dado em outro, i.e. como extrair a representação que quero a partir do dado que tenho.

Os exemplos clássicos para demonstrar esta diferença envolve a manipulação de listas.

Exemplo #1

Para calcular a somatória no estilo imperativo, é necessário pensar no controle sobre o estado da soma atual, que deve ser acumulado durante a iteração da lista.

int sum(int[] list) {
  int result = 0;
  for (int i : list)
    result += i;
  return result;
}

Do outro lado, no mundo funcional, é necessário pensar em como transformar uma lista em um único número que represente a soma de todos os elementos, i.e. a soma de uma lista vazia sempre será zero e a soma de qualquer outra lista é definida pelo seu primeiro valor acrescentado da soma do restante da lista.

sum [] = 0
sum (x:xs) = x + sum xs

Exemplo #2

Já em um exemplo um pouco mais complexo, em que precisamos manter duas listas no mundo imperativo, uma de entrada e outra de saída, precisamos incluir o controle sobre o índice de cada lista, para evitar erros de indexação.

String[] toText(int[] list) {
    String[] result = new String[list.length];
    for (int i = 0; i < list.length; ++i)
        result[i] = Integer.toString(list[i]);
    return result;
}

Enquanto que o mesmo exemplo no mundo funcional continua simples como a somatória da lista, a única diferença é que ao invés de transformarmos a lista utilizando a adição, utilizamos o próprio construtor de listas (representado pelo operador ':').

toText [] = []
toText (x:xs) = show x : toText xs

Motivação

Para demonstrar que o modelo funcional puro pode fazer muitas coisas além dos exemplos clássicos, de uma forma que considero bonita e com vantagens gratuitas, escrevo este post.

Calculadora

Hoje vamos criar uma calculadora em Haskell. Todo o código será puro, sem nenhum tipo de efeito colateral, incluindo uma DSL para escrever testes, o próprio executor dos testes e dois transformadores de cenários de teste, um para escrever o teste no formato de texto e outro para escrever o mesmo teste no formato de um JUnit.

Formato dos testes

Primeiramente, definimos o formato em que os testes serão escritos. Neste caso, será uma sequência de ações e validações:

data TestSequence =
    Do Action TestSequence
  | Check Assertion TestSequence
  | Done

Com esta estrutura de dados, os testes poderão ser escritos neste formato:

test =
  Do a.
  Do b.
  Do c.
  Check d$
  Done

A necessidade de ter o "Done" no final do teste me incomoda. Para evitar que precise escrever isto, indicarei que os testes sempre terminem de forma aberta, i.e. permitindo continuar a sequência:

type Test = TestSequence -> TestSequence

Agora podemos escrever o teste da seguinte forma:

test =
  Do a.
  Do b.
  Do c.
  Check d

Para mim, já está classificada como uma DSL funcional para testes.

O único tipo de ação disponível na calculadora é o de apertar seus botões e a única validação será a verificação do seu display. Os botões disponíveis são os padrões de uma calculadora.

data Action =
    Press Button

data Assertion =
    DisplayHasNumber Int

data Button =
    Zero
  | One
  | Two
  | Three
  | Four
  | Five
  | Six
  | Seven
  | Eight
  | Nine
  | Plus
  | Minus
  | Times
  | Divide
  | Equals
  | Clear
    deriving (Show)

Primeiro teste

O primeiro passo está pronto. Já temos uma DSL para testes compilando. Hora de escrever nosso primeiro teste, que também já compila:

sample :: Test
sample =
    Do (Press One).
    Do (Press Plus).
    Do (Press One).
    Do (Press Equals).
    Check (DisplayHasNumber 2).

    Do (Press Clear).
    Check (DisplayHasNumber 0).

    Do (Press Two).
    Do (Press Zero).
    Check (DisplayHasNumber 20).
    Do (Press Divide).
    Do (Press Two).
    Check (DisplayHasNumber 2).
    Do (Press Equals).
    Check (DisplayHasNumber 10)

Transformadores do teste

Como nosso teste está escrito na forma de uma estrutura de dados, isto nos dá muitas possibilidades para tratamento do caso de teste. Para facilitar as transformações desta estrutura, definimos uma função que aplica uma função genérica a cada passo do teste e agrupa os resultados em uma lista:

unroll :: (TestSequence -> a) -> Test -> [a]
unroll f t = g (t Done)
  where g Done = [f Done]
        g v@(Do _ next) = f v : g next
        g v@(Check _ next) = f v : g next

Teste -> Texto

Podemos processar o teste e gerar uma saída textual do cenário:

prettyPrint :: Test -> String
prettyPrint = unlines . unroll prettyPrintTestSequence

prettyPrintTestSequence :: TestSequence -> String
prettyPrintTestSequence s =
    case s of
      Done              -> "end"
      Do action _       -> prettyPrintAction action
      Check assertion _ -> prettyPrintAssertion assertion

prettyPrintAction :: Action -> String
prettyPrintAction (Press button) = 
    "press " ++ prettyPrintButton button

prettyPrintButton :: Button -> String
prettyPrintButton = map toLower . show

prettyPrintAssertion :: Assertion -> String
prettyPrintAssertion (DisplayHasNumber number) = 
    "the display should be showing the number " ++ 
    show number

Testando no GHCi:

\> putStr $ prettyPrint sample
press one
press plus
press one
press equals
the display should be showing the number 2
press clear
the display should be showing the number 0
press two
press zero
the display should be showing the number 20
press divide
press two
the display should be showing the number 2
press equals
the display should be showing the number 10
end

Teste -> JUnit

Também podemos gerar casos de teste para uma possível solução Java da nossa calculadora:

generateJUnit :: Test -> String
generateJUnit = 
    ("@Test\npublic void test() {\n" ++) . 
    unlines .
    unroll generateJUnitTestSequence

generateJUnitTestSequence :: TestSequence -> String
generateJUnitTestSequence s =
    case s of
      Done      -> "}"
      Do a _    -> generateJUnitAction a
      Check a _ -> generateJUnitAssertion a

generateJUnitAction :: Action -> String
generateJUnitAction (Press b) =
    generateJUnitButton b ++ ".press();"

generateJUnitButton :: Button -> String
generateJUnitButton b = "getButton" ++ show b ++ "()"

generateJUnitAssertion :: Assertion -> String
generateJUnitAssertion (DisplayHasNumber n) =
    "assertEquals(" ++ show n ++ ", getDisplayNumber());"

Testando no GHCi:

\> putStr $ generateJUnit sample
@Test
public void test() {
getButtonOne().press();
getButtonPlus().press();
getButtonOne().press();
getButtonEquals().press();
assertEquals(2, getDisplayNumber());
getButtonClear().press();
assertEquals(0, getDisplayNumber());
getButtonTwo().press();
getButtonZero().press();
assertEquals(20, getDisplayNumber());
getButtonDivide().press();
getButtonTwo().press();
assertEquals(2, getDisplayNumber());
getButtonEquals().press();
assertEquals(10, getDisplayNumber());
}

Teste de fato

E claro, também podemos utilizar nosso teste no formato de uma estrutura de dados para realmente testar uma calculadora:

data TestResult =
    Ok
  | Failed FailureMessage

type FailureMessage = String

instance Show TestResult where
    show Ok = "Test passed"
    show (Failed m) = "Test failed: " ++ m

checkTest :: Test -> TestResult
checkTest t = 
    evalState 
    (threadCheckState . unroll checkTestSequence $ t)
    mkCalculator

threadCheckState :: [State Calculator TestResult] ->
                    State Calculator TestResult 
threadCheckState = go 0
  where go _ [] = return Ok
        go n (x:xs) = x >>= (f n xs)
        f n xs Ok = go (n + 1) xs
        f n _ (Failed m) = 
          return . Failed $
            "Step " ++ show n ++ ". " ++ m

checkTestSequence :: TestSequence -> 
                     State Calculator TestResult
checkTestSequence Done = return Ok
checkTestSequence (Do a _) = checkAction a
checkTestSequence (Check a _) = checkAssertion a

checkAction :: Action -> State Calculator TestResult
checkAction (Press b) = do
    modify $ pressButton b 
    return Ok

checkAssertion :: Assertion -> State Calculator TestResult
checkAssertion (DisplayHasNumber n) =
    get >>= \c ->
      if displayNumber c == n
        then return Ok
        else return . Failed $ 
          "Wrong number in display, should be " ++
          show n ++ " but was " ++ show (displayNumber c)

O coração da calculadora

Finalmente, para que o testador-de-fato compile, precisamos definir uma primeira versão da nossa calculadora. Aqui você poderia tentar criar sua própria implementação. Cheguei neste código para atender ao cenário do teste:

data Calculator = Calculator {
    displayNumber :: Int
  , operation :: Maybe (Int -> Int -> Int)
  , savedNumber :: Int
  }

pressButton :: Button -> Calculator -> Calculator
pressButton b =
  case b of
    Zero    -> appendNumber 0
    One     -> appendNumber 1
    Two     -> appendNumber 2
    Three   -> appendNumber 3
    Four    -> appendNumber 4
    Five    -> appendNumber 5
    Six     -> appendNumber 6
    Seven   -> appendNumber 7
    Eight   -> appendNumber 8
    Nine    -> appendNumber 9
    Plus    -> saveOperation (+)
    Minus   -> saveOperation (-)
    Times   -> saveOperation (*)
    Divide  -> saveOperation div
    Equals  -> performOperation
    Clear   -> clear

appendNumber :: Int -> Calculator -> Calculator
appendNumber i c = 
  c { 
    displayNumber = (displayNumber c) * 10 + i 
  }

saveOperation :: (Int -> Int -> Int) -> 
                 Calculator -> Calculator
saveOperation f c = 
  c { 
    savedNumber = (displayNumber c)
  , displayNumber = 0
  , operation = Just f
  }

performOperation :: Calculator -> Calculator
performOperation c = 
  c { 
    savedNumber = newNumber
  , displayNumber = newNumber 
  }
  where newNumber = 
          case (operation c) of
            Nothing -> displayNumber c
            Just f  -> let a = savedNumber c
                           b = displayNumber c 
                        in
                           f a b

clear :: Calculator -> Calculator
clear = const mkCalculator

mkCalculator :: Calculator
mkCalculator = 
  Calculator { 
    displayNumber = 0
  , operation = Nothing
  , savedNumber = 0
  }

Testando a calculadora

Agora podemos executar o testador-de-fato contra nossa calculadora no GHCi. Vamos experimentar:

\> checkTest sample
Test passed

Isto significa que nossa calculadora está atendendo ao cenário de teste. Para garantir que o teste capture um comportamento que não corresponda ao cenário de teste, podemos introduzir um erro: alteramos o valor da multiplicação na função "appendNumber" de "10" para "100". Se rodarmos novamente o teste, teremos este resultado:

\> checkTest sample
Test failed: Step 9. Wrong number in display, should be 20 but was 200

Magavilha.

Conclusão

Construímos um código básico de uma calculadora funcionando que atende ao especificado no cenário de teste. Agora basta adicionarmos novos testes e continuar incrementando nossa calculadora, parecido com um TDD. Tudo isto foi feito de uma forma 100% pura, sem depender de nada que envolva IO, estado, variáveis ou logs.

Além do benefício de podermos fazer qualquer tipo de transformação nos cenários de teste, também podemos rodar quantas transformações e quantos testes quisermos de forma paralela, pois tanto o teste quanto a calculadora são thread-safe pelo simples fato de serem escritos de forma pura.

Conseguimos fazer tudo isto em míseras 251 linhas de código ou 5635 caracteres, incluindo comentários e linhas em branco. Quantas classes e/ou linhas seriam necessárias para contemplar todas as funcionalidades e seguranças demonstradas neste post na sua linguagem imperativa favorita?

Espero que este post sirva para inspirar vossas mentes a pensar "fora-da-caixa" do mundo imperativo. Existem muitas vantagens em aprender uma linguagem funcional pura, mesmo que você utilize linguagens imperativas para trabalhar.

O código inteiro está disponível no GitHub: https://gist.github.com/3354394. Para testar, é só baixar o código e carregar no GHCi.

Exemplos reais

Apenas para finalizar, alguns exemplos de aplicativos reais em uso desenvolvidos em Haskell:

12 de agosto de 2012

Criando um jogo de labirinto em Haskell

Quando eu estava aprendendo a programar em C, eu fiz vários pequenos projetos para colocar meu conhecimento à prova.

É muito bom olhar estes códigos antigos e perceber que aprendi muito nestes anos. Também é prazeroso ver que mesmo sem conhecer quase nada, consegui fazer muitas coisas divertidas.

Uma das primeiras coisas que fiz em C, foi um jogo de labirinto para terminal do Windows. Fiquei inacreditavelmente feliz e me achando muito inteligente por conseguir fazer um jogo assim.

Após algum tempo já programando, depois de conhecer a biblioteca SDL para criar jogos gráficos em C, o joguinho de labirinto chegou na sua terceira versão: DuDuRoX.

Como agora estou aprendendo Haskell e quero manter a tradição, irei criar um novo DuDuRoX nesta linguagem: DuDuHoX. Notem a pequena variação no nome demonstrando minha imensa criatividade.

Quem quiser acompanhar o progresso e fazer comentários, todo o código está disponível no GitHub (link no parágrafo acima).

Bastantes coisas já estão funcionando, até já é possível jogar. Quem quiser experimentar, é só baixar a plataforma Haskell, fazer um clone do repositório, executar o comando cabal install na pasta do jogo e ele estará disponível no seu terminal como "DuDuHoX".

Quem quiser dar uma olhada em códigos antigos, meus primeiros passos na programação estão postados no site Viva O Linux:

Alguns códigos mais "avançados", acabei não compartilhando, porém tenho eles salvos no meu computador, se alguém se interessar posso compartilhar também:

  • MultiMines: Jogo de campo minado.
  • HChess: Jogo de xadrez.
  • ObjectDetector: Tratador de imagem para realçar as bordas de objetos.
  • LConv: Conversor de "linguagens", a partir de uma pseudo-linguagem, o usuário conseguia definir regras de criptografia e aplicar a textos.
  • GATesting: Algoritmo genético para encontrar qualquer formula matemática que trouxesse como resultado o valor informado.